#ifndef __PRORITY_QUEUE_H__
#define __PRORITY_QUEUE_H__

#include <cstddef>
#include <stdexcept>
#include <vector>

// 默认是最大堆
template <typename T, typename Compare = std::less<T>>
class PriorityQueue
{
  public:
    PriorityQueue();
    ~PriorityQueue();

    void push(const T& data);

    void push(T&& data);

    void pop();

    const T& top() const;

    bool empty() const;

    size_t size() const;

  private:
    void heapify_down(const int index);
    void heapify_up(const int index);

    std::vector<T> heap;

    Compare compare;
};

template <typename T, typename Compare>
PriorityQueue<T, Compare>::PriorityQueue()
{
}

template <typename T, typename Compare>
PriorityQueue<T, Compare>::~PriorityQueue()
{
}

template <typename T, typename Compare>
void PriorityQueue<T, Compare>::push(const T& data)
{
    heap.push_back(data);
    heapify_up(heap.size() - 1);
}

template <typename T, typename Compare>
void PriorityQueue<T, Compare>::push(T&& data)
{
    heap.emplace_back(std::move(data));
    heapify_up(heap.size() - 1);
}

template <typename T, typename Compare>
void PriorityQueue<T, Compare>::pop()
{
    if (heap.empty())
        throw std::runtime_error("queue is empty");

    heap[0] = heap[heap.size() - 1];
    heap.pop_back();

    if (heap.size())
    {
        heapify_down(0);
    }
}

template <typename T, typename Compare>
const T& PriorityQueue<T, Compare>::top() const
{
    if (heap.empty())
        throw std::runtime_error("queue is empty");

    return heap[0];
}

template <typename T, typename Compare>
bool PriorityQueue<T, Compare>::empty() const
{
    return heap.empty();
}

template <typename T, typename Compare>
size_t PriorityQueue<T, Compare>::size() const
{
    return heap.size();
}

template <typename T, typename Compare>
void PriorityQueue<T, Compare>::heapify_down(const int index)
{
    if (index < 0 || index >= heap.size())
        return;

    int left = index + index + 1;   // 2*n + 1
    int right = index + index + 2;  // 2*n + 2

    int targetIndex = index;

    if (left < heap.size() && compare(heap[targetIndex], heap[left]))
    {
        targetIndex = left;
    }
    if (right < heap.size() && compare(heap[targetIndex], heap[right]))
    {
        targetIndex = right;
    }

    if (index != targetIndex)
    {
        std::swap(heap[index], heap[targetIndex]);
        heapify_down(targetIndex);
    }
}

template <typename T, typename Compare>
void PriorityQueue<T, Compare>::heapify_up(const int index)
{
    if (index <= 0 || index >= heap.size())
        return;

    int parentIndex = (index - 1) / 2;
    if (compare(heap[parentIndex], heap[index]))
    {
        std::swap(heap[index], heap[parentIndex]);
        heapify_up(parentIndex);
    }
}

#endif  //__PRORITY_QUEUE_H__